package offer.secnod;

public class Offer13 {
 int m,n,k;
    boolean[][] record;
    int movingCount(int m,int n,int k){
        this.m=m;
        this.n=n;
        this.k=k;
  record =new boolean[m][n];
  //TODO:2023/8/21 这样子算出来的结果不对
//    int count=0;
//        for (int x = 0; x <m ; x++) {
//            for (int y = 0; y < n; y++) {
//                if (sum(x)+sum(y)<k){
//                    count++;
//                }
//            }
//        }
//        return  count;
        return  find(0,0,k);
     }

    int sum(int x){
        int sum=0;
        while (x>0){
            sum+=x%10;
            x=x/10;
        }
        return  sum;
    }
   //TODO:2023/8/21 不太懂的
    int find(int x,int y,int k){
        if (x>=m||x<0||y>=n||y<0||sum(x)+sum(y)>k||record[x][y]){
            return  0;
        }
        record[x][y]=true;
//        todo: 从0，0出发 这样子以后就只用向右 向下 进行遍历
        return  1+find(x+1,y,k)+find(x,y+1,k);
    }


}
